public class Solution {
    //前n个数字二进制中1的个数
    public int[] countBits(int num) {
        int[] arr = new int[num+1];
        for(int i = 0; i <= num; i++) {
            int n = i;
            while (n != 0) {
                 n = n & (n-1);
                 arr[i]++;
            }
        }
        return arr;
    }
    //使用动态规划
    public int[] dbCountBits(int num) {
        int[] result = new int[num+1];
        result[0] = 0;
        for (int i = 1; i <= num ; i++) {
            result[i] = result[i & (i-1)] +1;
        }
        return result;
    }
}
